# -*- coding:utf-8 -*-
# 二分查找

# 1. 无重复数据
def binarySearch(list, item):
    left = 0
    right = len(list) - 1

    while (left <= right):
        mid = (left + right) // 2 # 计算 mid 时需要技巧防止溢出，建议写成: mid = left + (right - left) // 2
        if list[mid] == item:
            return mid
        elif list[mid] < item:
            left = mid + 1
        elif list[mid] > item:
            right = mid - 1
    return -1

# 2. 如果有重复，找出第一个位置，和3类似
def duplicateBinarySearch(list, item):
    left = 0
    right = len(list) - 1

    while (left <= right):
        mid = (left + right) // 2
        if item > list[mid]:
            left = mid + 1
        elif item <= list[mid]:
            right = mid - 1

    # 怎样返回-1，代表没找到？
    if left == len(list):
        return -1

    if list[left] == item:
        return left
    else:
        return -1

# 3. 寻找左侧边界
def left_bound(list, item):
    left = 0
    right = len(list)

    while (left < right):
        mid = (left + right) // 2
        if item == list[mid]:
            right = mid
        elif item > list[mid]:
            left = mid + 1
        elif item < list[mid]:
            right = mid
    
    # 考虑越界问题
    if left == len(list):
        return -1

    if list[left] == item:
        return left
    else:
        return -1


# 4. 寻找右侧边界
def right_bound(list, item):
    left = 0
    right = len(list)

    while (left < right):
        mid = (left + right) // 2
        if item == list[mid]:
            left = mid + 1
        elif item > list[mid]:
            left = mid + 1
        elif item < list[mid]:
            right = mid
    
    # 考虑越界问题
    if left == 0:
        return -1
    if list[left - 1] == item:
        return left - 1
    else:
        return -1


mylist = [12, 23, 24, 34, 45, 45, 78] # 二分查找要求是有序列表
res = right_bound(mylist, 45)
print(res)